TOC-Undecidability and Reducibility

Halting Problem

Formally , Mr. Naive wants to design a TM to decide ( not recognize ) the language.

$$HALT=\{<M,w>|TMMhaltsoninputw\}.$$

However, this is only Mr. Naive’s daydreaming. This problem is mission impossible.

[!abstract]+ Theorem HALT is undecidable.

The sketch of the proof is as follows.

• Assume $HALT$ is decidable.
• Thus, there is a TM $M$ decides $HALT$.
• Construct a string $x$ in ${\mathrm{\Sigma }}^{\ast }$ such that
  • $M$ accepts $x$ only if $M$ rejects $x$, and
  • $M$ rejects $x$ only if $M$ accepts $x$; which is a contradiction.

Reduction

To prove “a language is undecidable” is not easy at all.

The idea of reduction is rather simple. It is used to prove one problem (deciding a language ) is no easier than another problem.

Assume we want to reduce problem $A$ to problem $B$. First, we assume $B$ is "solvable". Then, there must be a machine $M_B$ to solve $B$. Next, we try to construct a machine $M_A$ to solve $A$ by making function calls to $M_B$. Those function calls are like an oracle in a blackbox. In consequence, if $M_B$ solves $B$, then $M_A$ solves $A$. The conclusion will be "if B is solvable, then so is A". Intuitively, problem $B$ is no easier than $A$. And we denote $A\le B$.